// 树的三种遍历递归和非递归版本、树宽度优先遍历、给定前序遍历和中序遍历构建二叉树
#include <iostream>
#include <stack>
#include <queue>

struct TreeNode
{
    int _value;
    TreeNode *_left_node;
    TreeNode *_right_node;

    TreeNode(int value)
        : _value(value), _left_node(nullptr), _right_node(nullptr) {}
};

// 前序遍历
void Print1(TreeNode *node)
{
    if (node == nullptr)
        return;

    std::cout << node->_value << " ";
    Print1(node->_left_node);
    Print1(node->_right_node);
}
// 非递归版本
void PreorderPrint(TreeNode *node)
{
    if (node == nullptr)
        return;

    std::stack<TreeNode *> st;
    st.push(node);

    while (!st.empty())
    {
        TreeNode *tmp = st.top();
        st.pop();
        std::cout << tmp->_value << " ";

        if (tmp->_right_node != nullptr)
            st.push(tmp->_right_node);
        if (tmp->_left_node != nullptr)
            st.push(tmp->_left_node);
    }
}

// 中序遍历
void Print2(TreeNode *node)
{
    if (node == nullptr)
        return;

    Print2(node->_left_node);
    std::cout << node->_value << " ";
    Print2(node->_right_node);
}
// 非递归版本
void InorderPrint(TreeNode *node)
{
    if (node == nullptr)
        return;

    std::stack<TreeNode *> st;

    TreeNode *cur = node;
    while (cur != nullptr || !st.empty())
    {
        // 找到最左节点
        while (cur != nullptr)
        {
            st.push(cur);
            cur = cur->_left_node;
        }
        // 之后打印最左面的节点
        if (!st.empty())
        {
            TreeNode *tmp = st.top();
            std::cout << tmp->_value << " ";
            st.pop();
            // 开始处理最左节点的右子树
            cur = tmp->_right_node;
        }
    }
}

// 后序遍历
void Print3(TreeNode *node)
{
    if (node == nullptr)
        return;

    Print3(node->_left_node);
    Print3(node->_right_node);
    std::cout << node->_value << " ";
}
// 非递归版本
void PostOrderPrint(TreeNode *node)
{
    if (node == nullptr)
        return;

    std::stack<TreeNode *> st;
    TreeNode *cur = node;
    TreeNode *prev = nullptr;

    // 当左节点全部遍历完毕，要开始遍历右节点时，st就式空的
    while (cur != nullptr || !st.empty())
    {
        // 找到最左节点
        while (cur != nullptr)
        {
            st.push(cur);
            cur = cur->_left_node;
        }

        if (!st.empty())
        {
            cur = st.top();
            // 没有右节点或者右节点已经访问过了
            if (cur->_right_node == nullptr || cur->_right_node == prev)
            {
                std::cout << cur->_value << " ";
                st.pop();
                prev = cur;
                cur = nullptr; // 防止当前节点又被压入栈中
            }
            else
            {
                cur = cur->_right_node;
            }
        }
    }
}

// 宽度优先遍历
void LevelOrderPrint(TreeNode *node)
{
    if (node == nullptr)
        return;

    std::queue<TreeNode *> q;
    q.push(node);

    // 遍历
    while (!q.empty())
    {
        TreeNode *tmp = q.front();
        q.pop();
        std::cout << tmp->_value << " ";

        if (tmp->_left_node != nullptr)
            q.push(tmp->_left_node);
        if (tmp->_right_node != nullptr)
            q.push(tmp->_right_node);
    }
}

// 重建二叉树
TreeNode *_ReplaceCraeteTree(int *preorderStart, int *preorderEnd, int *inorderStart, int *inorderEnd)
{
    // 找到根节点，并创建根节点
    int value = preorderStart[0];
    TreeNode *node = new TreeNode(value);

    // 如果是叶子节点了，那么就直接返回即可
    if (preorderStart == preorderEnd)
    {
        if (inorderStart == inorderEnd && *preorderStart == *inorderStart)
            return node;
        else
        {
            std::cout << *preorderStart << " " << *inorderStart << std::endl;
            return nullptr;
        }
    }
    // 找到根节点在中序所在的位置，创建子节点
    int *index = inorderStart;
    while (index <= inorderEnd && *index != value)
        index++;
    // 如果没有找到的话
    if (index > inorderEnd)
    {
        std::cout << "2" << std::endl;
        return nullptr;
    }

    // 计算左面的长度
    int left_length = index - inorderStart;
    int *preorderLeft = preorderStart + left_length;
    // 构建左子树
    if (left_length > 0)
    {
        node->_left_node = _ReplaceCraeteTree(preorderStart + 1, preorderLeft, inorderStart, index - 1);
    }
    // 构建右子树
    if (preorderEnd - preorderStart > left_length)
    {
        node->_right_node = _ReplaceCraeteTree(preorderLeft + 1, preorderEnd, index + 1, inorderEnd);
    }
    return node;
}

TreeNode *ReplaceCreateTree(int *preorder, int *inorder, int length)
{
    if (preorder == nullptr || inorder == nullptr || length == 0)
        return nullptr;

    return _ReplaceCraeteTree(preorder, preorder + length - 1, inorder, inorder + length - 1);
}

// int main()
// {
//     TreeNode* node1 = new TreeNode(10);
//     TreeNode* node2 = new TreeNode(6);
//     TreeNode* node3 = new TreeNode(14);

//     node1->_left_node = node2;
//     node1->_right_node = node3;

//     node2->_left_node = new TreeNode(4);
//     node2->_right_node = new TreeNode(8);
//     node3->_left_node = new TreeNode(12);
//     node3->_right_node = new TreeNode(16);

//     PreorderPrint(node1);
//     std::cout << std::endl;
//     InorderPrint(node1);
//     std::cout << std::endl;
//     PostOrderPrint(node1);
//     std::cout << std::endl;
//     LevelOrderPrint(node1);
//     std::cout << std::endl;
//     return 0;
// }

int main()
{
    // int preorder[8] = {1,2,4,7,3,5,6,8};
    // int inorder[8] = {4,7,2,1,5,3,8,6};
    // TreeNode* node = ReplaceCreateTree(preorder, inorder, 8);
    // LevelOrderPrint(node);
    // std::cout << std::endl;

    // int preorder[4] = {1, 2, 3, 4};
    // int inorder[4] = {4, 3, 2, 1};
    // TreeNode *node = ReplaceCreateTree(preorder, inorder, 4);
    // LevelOrderPrint(node);
    // std::cout << std::endl;

    // int preorder[4] = {1};
    // int inorder[4] = {1};
    // TreeNode *node = ReplaceCreateTree(preorder, inorder, 1);
    // LevelOrderPrint(node);
    // std::cout << std::endl;

    int preorder[4] = {1,2,3,4};
    int inorder[4] = {1,2,3,4};
    TreeNode *node = ReplaceCreateTree(preorder, inorder, 4);
    LevelOrderPrint(node);
    std::cout << std::endl;
    return 0;
}